//
// Created by Administrator on 2021/4/9.
//

/*
计算给定二叉树的所有左叶子之和。

示例：

3
/ \
  9  20
/  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-left-leaves
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
// Definition for a binary tree node.
#include <iostream>
#include <queue>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
};

class Solution {
private:
    int sumVal = 0;
public:
    // 左叶子之和  首先必须是叶子 ——》左 右 指针为空
    // 怎么判断是左边的叶子？
    int sumOfLeftLeaves(TreeNode *root) {
        if (root == nullptr) return 0;
        if (isLeaf(root->left)) {
            sumVal += root->left->val;
            sumOfLeftLeaves(root->right);
        } else {
            sumOfLeftLeaves(root->left);
            sumOfLeftLeaves(root->right);
        }
        return sumVal;
    }

    bool isLeaf(TreeNode *root) {
        return (root != nullptr) and (root->left == nullptr) and (root->right == nullptr);
    }
    // AC
};

class Solution2 { // 题解 dfs
public:
    bool isLeafNode(TreeNode *node) {
        return !node->left && !node->right;
    }

    int dfs(TreeNode *node) {
        int ans = 0;
        if (node->left) {
            ans += isLeafNode(node->left) ? node->left->val : dfs(node->left);
        }
        if (node->right && !isLeafNode(node->right)) {
            ans += dfs(node->right);
        }
        return ans;
    }

    int sumOfLeftLeaves(TreeNode *root) {
        return root ? dfs(root) : 0;
    }
};

class Solution3 { // 题解 bfs
public:
    bool isLeafNode(TreeNode *node) {
        return !node->left && !node->right;
    }

    int sumOfLeftLeaves(TreeNode *root) {
        if (!root) {
            return 0;
        }

        std::queue<TreeNode *> q;
        q.push(root);
        int ans = 0;
        while (!q.empty()) {
            TreeNode *node = q.front();
            q.pop();
            if (node->left) {
                if (isLeafNode(node->left)) {
                    ans += node->left->val;
                } else {
                    q.push(node->left);
                }
            }
            if (node->right) {
                if (!isLeafNode(node->right)) {
                    q.push(node->right);
                }
            }
        }
        return ans;
    }
};


int main() {
    auto t5 = TreeNode(7);
    auto t4 = TreeNode(15);
    auto t3 = TreeNode(20, &t4, &t5);
    auto t2 = TreeNode(9);
    auto t1 = TreeNode(3, &t2, &t3);
    Solution sol;
    std::cout << sol.sumOfLeftLeaves(&t1);
    return 0;
}